/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @author zhong
 *
 */
public class NumberofMatchingSubsequences {
	public int numMatchingSubseq(String S, String[] words) {
		HashMap<Character, ArrayList<Integer>> ch2poses = new HashMap<>(26);
		for (int i = 0; i < S.length(); i++) {
			char ch = S.charAt(i);
			if (!ch2poses.containsKey(ch)) {
				ArrayList<Integer> list = new ArrayList<>();
				list.add(i);
				ch2poses.put(ch, list);
			} else {
				ch2poses.get(ch).add(i);
			}
		}

		int res = 0;
		for (String string : words) {
			boolean isSub = true;

			int pos = -1;
			int[] indexes = new int[26];// 下一个要处理的
			for (int i = 0; i < string.length(); i++) {
				char ch = string.charAt(i);
				if (!ch2poses.containsKey(ch)) {// 如果S不包含该字符，则false
					isSub = false;
					break;
				}
				ArrayList<Integer> list = ch2poses.get(ch);
				while (indexes[ch - 'a'] < list.size() && list.get(indexes[ch - 'a']) <= pos) {
					indexes[ch - 'a']++;
				}
				if (indexes[ch - 'a'] == list.size()) {// 已经没有多余的该字符在S中
					isSub = false;
					break;
				}
				pos = list.get(indexes[ch - 'a']);
			}

			if (isSub) {
				System.out.println(string);
				res++;
			}
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String S = "abcde";
		String[] words = { "a", "bb", "acd", "ace" };
		System.out.println(new NumberofMatchingSubsequences().numMatchingSubseq(S, words));
	}

}
